/*	Program P12-5 Delete arc.
	
    Brooks/Cole Publishing Company
	An International Thomson Publishing Company
	Copyright 1998. All Rights Reserved
*/

/*	==================== deleteArc ====================
	Deletes an existing arc.
	   Pre    fromKey is key of start vertex and toKey is
	          key of the destination vertex to be deleted
	   Post   arc deleted 
	   Return success +1 if successful
	                  -2 if fromKey not found
	                  -3 if toKey not found
*/

template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> :: deleteArc (KTYPE  fromKey,
                                     KTYPE  toKey)
{
//	Local Definitions 
	Vertex<TYPE>  *fromVertexPtr;
	Vertex<TYPE>  *toVertexPtr;
	Arc<TYPE>     *preArcPtr;
	Arc<TYPE>     *arcWalkPtr;

//	Statements 
	if (!first)
	    return -2;

   //	Locate source vertex 
	fromVertexPtr = first;
	while (fromVertexPtr 
	       && fromKey > (fromVertexPtr->data).key)
	    fromVertexPtr = fromVertexPtr->pNextVertex;

	if (!fromVertexPtr 
	     || fromKey != (fromVertexPtr->data).key)
	   return -2;
	   
	//  Locate destination vertex in adjacency list 
	if (!fromVertexPtr->pArc)
	    return -3;
	
	preArcPtr  = NULL;
	arcWalkPtr = fromVertexPtr->pArc;
	while (arcWalkPtr 
	   && toKey > (arcWalkPtr->destination->data).key)
	   {
	    preArcPtr  = arcWalkPtr;
	    arcWalkPtr = arcWalkPtr->pNextArc;
	   } // while arcWalkPtr && 
	if (!arcWalkPtr 
	    || toKey  != (arcWalkPtr->destination->data.key))
	    return -3;
	toVertexPtr = arcWalkPtr->destination;
	
	// fromVertex, toVertex, and arcPtr located. Delete arc.
	--fromVertexPtr->outDegree;     
	--toVertexPtr->inDegree;
	if (!preArcPtr)
	    // Deleting first arc 
	    fromVertexPtr->pArc  = arcWalkPtr->pNextArc;
	else
	    preArcPtr->pNextArc = arcWalkPtr->pNextArc;
	delete arcWalkPtr;
	return 1;
}  // deleteArc 
